package class04;

import java.util.Arrays;

/**
 * 归并排序：时间复杂度 O(n·log·n)  |  空间复杂度 O(log n)
 *
 * <a href="https://leetcode.cn/problems/sort-an-array/">912. 排序数组</a>
 */
public class Code01_MergeSort {

    // 递归写法
    public static void mergeSort1(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    // 非递归写法
    public static void mergeSort2(int[] arr) {
        int mergeSize = 1, N = arr.length;
        while (mergeSize < N) {
            int L = 0;
            while (L < N) {
                if (mergeSize >= N - L) {
                    break;
                }
                int M = L + mergeSize - 1;
                int R = Math.min(M + mergeSize, N - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            if (mergeSize > N / 2) {  // 防溢出
                break;
            }
            mergeSize >>= 1;  // 每次扩大两倍
        }
    }

    private static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int M = L + ((R - L) >> 1);
        process(arr, L, M);
        process(arr, M + 1, R);
        merge(arr, L, M, R);
    }

    private static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int l = L, r = M + 1, index = 0;
        while (l <= M || r <= R) {
            if (l > M) {
                help[index++] = arr[r++];
            } else if (r > R) {
                help[index++] = arr[l++];
            } else {
                help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
            }
        }
        System.arraycopy(help, 0, arr, L, help.length);
    }

    public static boolean isEquals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; ++i) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[(int) (Math.random() * (30 - 1) + 1)];
        for (int i = 0; i < arr1.length; ++i) {
            arr1[i] = (int) (Math.random() * (100 - 1) + 1);
        }
        mergeSort1(arr1);
        System.out.println(Arrays.toString(arr1));
        int[] arr2 = arr1.clone();
        mergeSort1(arr2);
        System.out.println(Arrays.toString(arr2));
        if (isEquals(arr1, arr2)) {
            System.out.println("相同");
        } else {
            System.out.println("不相同");
        }
    }
}
